import java.util.*;

class MyTree{

    static class TreeNode{
        int num;
        TreeNode left;
        TreeNode right;

        TreeNode(int n){
            num=n;
        }

    }

    public TreeNode root;

    public void creattree(){
        TreeNode t1=new TreeNode(1);
        TreeNode t2=new TreeNode(2);
        TreeNode t3=new TreeNode(3);
        TreeNode t4=new TreeNode(4);
        TreeNode t5=new TreeNode(5);
        TreeNode t6=new TreeNode(6);
        TreeNode t7=new TreeNode(7);
        TreeNode t8=new TreeNode(8);

        t1.left=t2;
        t1.right=t3;
        t2.right=t4;
        t3.left=t5;
        t4.left=t6;
        t5.left=t7;
        t5.right=t8;

        root=t1;
    }

    public void DGPreOrder(TreeNode root){
        if(root==null)
            return;
        System.out.print(root.num+" ");
        DGPreOrder(root.left);
        DGPreOrder(root.right);

    }

//    public void Preorder(TreeNode root){
//        if (root==null)
//            return;
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur=root;
//        TreeNode top=null;
//
//        while (cur != null || !stack.empty()) {
//
//            while(cur!=null){
//                stack.push(cur);
//                System.out.print(cur.num+" ");
//                cur=cur.left;
//            }
//
//            top=stack.pop();
//            cur=top.right;
//        }

        public List<Integer> preorderTraversal(TreeNode root){
            ArrayList<Integer> arrayList=new ArrayList<>();
            if (root==null)
                return arrayList;
            Stack<TreeNode> stack=new Stack<>();
            TreeNode cur=root;
            TreeNode top=null;

            while (cur != null || !stack.empty()) {

                while (cur != null) {
                    stack.push(cur);
                    arrayList.add(cur.num);
                    cur = cur.left;
                }

                top = stack.pop();
                cur = top.right;
            }
            return arrayList;
        }


    }


class Solution {

    static class TreeNode{
        int val;
        Solution.TreeNode left;
        Solution.TreeNode right;

        TreeNode(int n){
            val=n;
        }

        TreeNode(){}
    }

    //中序后续构造-----------------------------------
    private int j=0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return bulidsunTree(postorder,inorder,0,inorder.length-1);
    }

    private TreeNode bulidsunTree(int[] postorder,int[]inorder,int left,int right){
        if (j>postorder.length-1||left>right)
            return null;
        if (left==right){
            j++;
            return new TreeNode(inorder[left]);
        }
        int opn=postorder[postorder.length-j-1];
        TreeNode treeNode=new TreeNode(opn);
        j++;
        int ino=find(opn,inorder,left,right);
        treeNode.right=bulidsunTree(postorder,inorder,ino+1,right);
        treeNode.left=bulidsunTree(postorder,inorder,left,ino-1);
        return treeNode;
    }

    private int find(int obj,int[] inorder,int le,int ri){
        while(le<=ri){
            if(inorder[le]==obj)
                return le;
            le++;
        }
        return -1;
    }








//    //前序中序构造------------------------------------
//    private int i=0;
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return  buildsunTree(preorder,inorder,0,inorder.length-1);
//    }
//
//    private TreeNode buildsunTree(int[] preorder,int[] inorder,int left,int right){
//        if(i>preorder.length-1||left>right)
//            return null;
//        if (left==right){
//            return new TreeNode(preorder[i++]);
//        }
//        int tel = preorder[i++];
//        TreeNode treeNode=new TreeNode(tel);
//        int goal=find(tel,inorder,left,right);
//        treeNode.left=buildsunTree(preorder,inorder,left,goal-1);
//        treeNode.right=buildsunTree(preorder, inorder, goal+1, right);
//        return treeNode;
//    }
//
//    private int find(int tel,int[] inorder,int le,int ri){
//        while(le<=ri){
//            if(tel==inorder[le])
//                return le;
//            le++;
//        }
//        return -1;
//    }




    public void DGPreOrder(Solution.TreeNode root){
        if(root==null)
            return;
        DGPreOrder(root.left);
        DGPreOrder(root.right);
        System.out.print(root.val+" ");
    }

}


class Grand{

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        boolean br=false;
//        if (root==p||root==q)
//            br=true;
//        if (root==p&&root.left==q||root==p&& root.right==q)
//            return p;
//        if (root==q&&root.left==p||root==q&& root.right==p)
//            return q;
//        boolean fl=find(root.left, p.val, q.val);
//        boolean fr=find(root.right, p.val, q.val);
//        if ((root.left==p&&root.right==q)||(root.left==q&& root.right==p)||(fl&&fr)||(fl&&br)||(br&&fr))
//            return root;
//        if (fl)
//            return lowestCommonAncestor(root.left,p,q);
//        if (fr)
//            return lowestCommonAncestor(root.right,p,q);
//
//        return null;
//    }
//
//    private boolean find(TreeNode root,int f1,int f2){
//        if (root==null)
//            return false;
//        if (root.val==f1||root.val==f2)
//            return true;
//        return find(root.left,f1,f2)||find(root.right,f1,f2);
//    }


    TreeNode ans=null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        dfs(root,p,q);
        return ans;
    }


    public boolean dfs(TreeNode root,TreeNode p,TreeNode q){
        if (root==null)
            return false;
        boolean bl=dfs(root.left,p,q);
        boolean br=dfs(root.right,p,q);
        if ((bl&&br)||((bl||br)&&(root==p||root==q)))
            ans=root;
        return (bl||br||root==p||root==q);
    }




    public void bulidTree(){
        TreeNode treeNode0=new TreeNode(0);
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(5);
        TreeNode treeNode6=new TreeNode(6);
        TreeNode treeNode7=new TreeNode(7);
        TreeNode treeNode8=new TreeNode(8);

        treeNode3.left=treeNode5;
        treeNode3.right=treeNode1;
        treeNode5.left=treeNode6;
        treeNode5.right=treeNode2;
        treeNode1.left=treeNode0;
        treeNode1.right=treeNode8;
        treeNode2.left=treeNode7;
        treeNode2.right=treeNode4;

        root=treeNode3;

        t1=treeNode5;
        t2=treeNode4;

    }

    public void DGPreOrder(TreeNode root){
        if(root==null)
            return;
        System.out.print(root.val+" ");
        DGPreOrder(root.left);
        DGPreOrder(root.right);
    }

    public TreeNode root;


    public TreeNode t1;
    public TreeNode t2;


}


class Order {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root==null)
            return new ArrayList<>();

        Stack<List<Integer>> stack=new Stack<>();
        Queue<TreeNode> queue=new LinkedList<>();

        queue.add(root);
        int cak=1;

        while(!queue.isEmpty()){
            int tep=0;
            List<Integer> slist=new ArrayList<>();
            while(cak!=0){
                TreeNode treeNode=queue.poll();
                if (treeNode != null && treeNode.left != null) {
                    queue.add(treeNode.left);
                    tep++;
                }
                if (treeNode != null && treeNode.right != null) {
                    queue.add(treeNode.right);
                    tep++;
                }
                if (treeNode != null) {
                    slist.add(treeNode.val);
                }

                cak--;
            }
            stack.push(slist);
            cak=tep;

        }

        List<List<Integer>> listList=new ArrayList<>();

        while(!stack.empty()){
            listList.add(stack.pop());
        }

        return listList;
    }

    void creatTree(){

        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode9=new TreeNode(9);
        TreeNode treeNode20=new TreeNode(20);
        TreeNode treeNode15=new TreeNode(15);
        TreeNode treeNode7=new TreeNode(7);

        treeNode3.left=treeNode9;
        treeNode3.right=treeNode20;
        treeNode20.left=treeNode15;
        treeNode20.right=treeNode7;

        root=treeNode3;

    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null)
            return new LinkedList<>();

        List<List<Integer>> listList=new LinkedList<>();
        Queue<TreeNode> queue=new LinkedList<>();

        queue.add(root);
        int cak=1;

        while(!queue.isEmpty()){
            int tep=0;
            List<Integer> list=new LinkedList<>();
            while(cak!=0){
                TreeNode treeNode=queue.poll();
                if (treeNode.left!=null){
                    queue.add(treeNode.left);
                    tep++;
                }
                if (treeNode.right!=null) {
                    queue.add(treeNode.right);
                    tep++;
                }
                list.add(treeNode.val);

                cak--;
            }
            listList.add(list);
            cak=tep;
        }

        return listList;
    }



    TreeNode root;

}



class BuildString{

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    void bulidTree(){

        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;

        root=treeNode1;
    }


    void bulidTree2(){

        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.right=treeNode4;

        root=treeNode1;
    }


    public String tree2str(TreeNode root) {

        if (root==null)
            return null;

        StringBuffer stringBuffer=new StringBuffer();
        stringBuffer.append(root.val);

        String sleft=tree2str(root.left);
        String sright=tree2str(root.right);

        if (sleft!=null||sright!=null){

            if (sleft==null&&sright!=null){
                stringBuffer.append("()");
                stringBuffer.append("(");
                stringBuffer.append(sright);
                stringBuffer.append(")");

//                sleft="()";
//                stringBuffer.append(sleft);
//                stringBuffer.append(sright);
            } else if (sleft != null && sright == null) {
                stringBuffer.append("(");
                stringBuffer.append(sleft);
                stringBuffer.append(")");

            }else {
                stringBuffer.append("(");
                stringBuffer.append(sleft);
                stringBuffer.append(")");
                stringBuffer.append("(");
                stringBuffer.append(sright);
                stringBuffer.append(")");
            }

//            stringBuffer.append(")");

            return new String(stringBuffer);
        }else {
//            StringBuffer stringBuffer1=new StringBuffer("("+stringBuffer+")");
            return new String(stringBuffer);
        }

    }

    public String tree2str_better(TreeNode root){
        if (root==null)
            return "";
        if (root.left==null&&root.right==null){
            return Integer.toString(root.val);
        } else if (root.right==null) {
            return new StringBuffer().append(root.val).append("(").append(tree2str_better(root.left)).append(")").toString();
        }else {
            return new StringBuffer().append(root.val).append("(").append(tree2str_better(root.left)).append(")(").append(tree2str_better(root.right)).append(")").toString();
        }
    }

    public TreeNode root;

}



class PosterOrder{

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root==null)
            return new ArrayList<>();

        Stack<TreeNode> nodeStack=new Stack<>();
        Stack<Integer> integerStack=new Stack<>();

        nodeStack.push(root);

        while(!nodeStack.empty()){
            TreeNode treeNode=nodeStack.pop();
            if (treeNode.left!=null){
                nodeStack.push(treeNode.left);
            }
            if (treeNode.right!=null){
                nodeStack.push(treeNode.right);
            }
            integerStack.push(treeNode.val);

        }

        List<Integer> list=new ArrayList<>();

        while(!integerStack.empty()){
            list.add(integerStack.pop());
        }

        return list;
    }

    public void bulidTree(){

        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(5);
        TreeNode treeNode6=new TreeNode(6);
        TreeNode treeNode7=new TreeNode(7);
        TreeNode treeNode8=new TreeNode(8);
        TreeNode treeNode9=new TreeNode(9);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.right=treeNode8;
        treeNode5.left=treeNode6;
        treeNode5.right=treeNode7;
        treeNode8.left=treeNode9;

        root=treeNode1;

    }

    public TreeNode root;

}




public class Main {

    public static void main(String[] args) {
        PosterOrder posterOrder=new PosterOrder();

        posterOrder.bulidTree();

        System.out.println(posterOrder.postorderTraversal(posterOrder.root));

    }



    public static void main6(String[] args) {
        BuildString buildString= new BuildString();

        buildString.bulidTree();

        System.out.println(buildString.tree2str(buildString.root));

        buildString.bulidTree2();

        System.out.println(buildString.tree2str_better(buildString.root));

    }


    public static void main5(String[] args) {
        Order order=new Order();

        order.creatTree();

        List<List<Integer>> listList=order.levelOrderBottom(order.root);

        System.out.println(listList);

        listList=order.levelOrder(order.root);

        System.out.println(listList);

    }


    public static void main4(String[] args) {
        Grand grand=new Grand();
        grand.bulidTree();

        System.out.println(grand.lowestCommonAncestor(grand.root, grand.t1, grand.t2).val);

//        grand.DGPreOrder(grand.root);

    }


    public static void main3(String[] args) {
        int[] postorder = {2,1,4,3};
        int[] inorder = {1,2,3,4};

        Solution solution=new Solution();
        Solution.TreeNode treeNode=solution.buildTree(inorder,postorder);
        solution.DGPreOrder(treeNode);
    }


    public static void main2(String[] args) {
        int[] preorder = {1,2};
        int[] inorder = {1,2};

        Solution solution=new Solution();
        Solution.TreeNode treeNode=solution.buildTree(preorder,inorder);
        solution.DGPreOrder(treeNode);
    }

    public static void main1(String[] args) {
        MyTree myTree=new MyTree();
        myTree.creattree();

        myTree.DGPreOrder(myTree.root);
        System.out.println();
        System.out.println(myTree.preorderTraversal(myTree.root));

    }
}